Computational Game Theory

so far: given a game ⤳ analyse properties (e.g., equilibrium existence, computation, complexity, quality...)
now: given desired properties ⤳ design corresponding game → mechanism design

§5 Combinatorial Auctions

set of items to be sold
set of potential buyers (=players)
players have values for items (secret) and place bids for items (simultaneously)
based on bids, mechanism decides on allocation of items and payments

mechanism should be:

efficient: maximises social welfare
strategyproof: incentivises players to bid truthfully
computable: runs in polynomial time

§5.1 Vickrey Auction

a single item
set of players $N$ with (private) valuation $v_i \in \IRnn$
each player submits a single (sealed) bid $b_i \in \IRnn$
mechanism $M: \IRnn^N \to \set{0,1}^N \times \IRnn^N, b \mapsto (x,p)$
- $x$ allocation where $x_i=1 \iff$ player $i$ gets item
  ⤳ require $\sum_i x_i=1$
- $p$ payments where $p_i =$ payment of player $i$
  ⤳ require $p_i \leq x_i\cdot b_i$
$\implies$ $i$'s utility of $M(b)$ is $u_i(x,p) \coloneqq x_i\cdot(v_i-p_i)$

⤳ game $(N,\IRnn^N,u\circ M)$

Second-Price Auction

Input: bids $b \in \IRnn^N$
Output: allocation $x \in \set{0,1}^N$ and payments $p \in \IRnn^N$

choose $i \in \argmax_{j \in N}b_j$
set $x_i \leftarrow 1$ and $p_i \leftarrow \max_{j \neq i}b_j$
set $x_j \leftarrow 0$ and $p_j \leftarrow 0$ f.a. $j \neq i$

Thm. 5.2: Second-price auction is

strategyproof: $u_i(M(v_i,b_{-i})) \geq u_i(M(b_i,b_{-i}))$ f.a. $i \in N, b \in \IRnn^N$
efficient: maximises $\sum_i x_i v_i$ under truthful bidding
computable: runs in polynomial time

§5.2 Transport Coordination

directed graph $D=(V,E)$ with origin $o \in V$, destination $d \in V$
Goal: transport an item from $o$ to $d$
edges $e \in E$ are players with (private) costs $c_e \in \IRnn$
players make bids ("declared costs") $b_e \in \IRnn$
mechanism $M: \IRnn^N \to \set{0,1}^E \times \IRnn^N, b \mapsto (x,p)$
- $\set{e \in E \sMid x_e = 1}$ form $o,d$-path
- $p_e =$ payment to player $e$
$\implies$ $e$'s utility of $M(b)$ is $u_e(x,p) \coloneqq x_e\cdot(p_e-c_e)$

Mechanism KW

Input: bids $b \in \IRnn^E$
Output: allocation $x \in \set{0,1}^E$ and payments $p \in \IRnn^E$

compute shortest $o,d$-path $P$ wrt. edge costs $b_e$
set $x_e \leftarrow 1$ for $e \in P$ and $x_e \leftarrow 0$ else
For $e \in P$ Do
mm compute shortest $o,d$-path $P_{-e}$ in $G_{-e}$ wrt. $b_e$
mm set $p_e \leftarrow b_e + \bigl(\sum_{e' \in P_{-e}}b_{e'} - \sum_{e' \in P}b_{e'}\bigr)$

Thm. 5.4: Mechanism KW is strategyproof, efficient and polynomial (if no player has a monopoly position)

Second-Price Auction

Input: bids $b \in \IRnn^N$
Output: allocation $x \in \set{0,1}^N$ and payments $p \in \IRnn^N$

choose $i \in \argmax_{j \in N}b_j$
set $x_i \leftarrow 1$ and $p_i \leftarrow \max_{j \neq i}b_j$
set $x_j \leftarrow 0$ and $p_j \leftarrow 0$ f.a. $j \neq i$

§5.3 The VCG-Mechanism

multiple items $E=\set{1,\dots,m}$
multiple players/buyers $N = \set{1,\dots,n}$
set of possible allocations $X \coloneqq \set{x: E \to N \cup \set{\bot}}$
players have private valuation functions $v_i: X \to \IRnn$
and provide declared valuation functions $b_i: X \to \IRnn$ ("bids")
mechanism $M: (\IRnn^X)^N \to X \times \IRnn^N, b \mapsto (x,p)$
$\implies$ $e$'s utility of $M(b)$ is $u_e(x,p) \coloneqq v_i(x)-p_i$

VCG Mechanism

Input: bids $b \in \bigl(\IRnn^X\bigr)^N$
Output: allocation $x^* \in X$ and payments $p \in \IRnn^N$

determine $x^* \in \argmax_{x \in X}\sum_{i \in N}b_i(x)$
For $i \in N$ Do
mm determine $\bar x \in \argmax_{x \in X}\sum_{j \in N \setminus\set{i}}b_j(x)$
mm set $p_i \leftarrow b_i(x^*) + \sum_{j \neq i}b_j(\bar x) - \sum_{j \in N}b_j(x^*)$

Mechanism KW

Input: bids $b \in \IRnn^E$
Output: allocation $x \in \set{0,1}^E$ and payments $p \in \IRnn^E$

compute shortest $o,d$-path $P$ wrt. edge costs $b_e$
set $x_e \leftarrow 1$ for $e \in P$ and $x_e \leftarrow 0$ else
For $e \in P$ Do
mm compute shortest $o,d$-path $P_{-e}$ in $G_{-e}$ wrt. $b_e$
mm set $p_e \leftarrow b_e + \bigl(\sum_{e' \in P_{-e}}b_{e'} - \sum_{e' \in P}b_{e'}\bigr)$

Thm. 5.6: The VCG mechanism is strategyproof and efficient.

§5.4 Single-Minded Bidders

multiple items $E=\set{1,\dots,m}$
multiple players/buyers $N = \set{1,\dots,n}$
set of possible allocations $X \coloneqq \set{x: E \to N \cup \set{\bot}}$
every buyer wants exactly one bundle of items, i.e.
every player has $\emptyset \neq W_i \subseteq E$ and $w_i \in \IRnn$ with \[v_i(x) = \begin{cases}w_i, &\text{if } W_i \subseteq x^{-1}(i)\\0, &\text{else}\end{cases} \text{ for all } x \in X\]
every buyer declares bid $(B_i,b_i)$ with $B_i \subseteq E$, $b_i \in \IRnn$

Optimal Allocation for Single Minded Bidders (OAfSMB):
Input: players $N$, items $E$, bids $((B_i,b_i))_{i \in N}$
Output: set of winners $N^* \subseteq N$ with $B_i \cap B_j = \emptyset$ f.a. $i,j \in N^*$
Output: such that $\sum_{i \in N^*}b_i$ maximal

Thm. 5.7: OAfSMB is NP-hard.

mechanism is $\alpha$-efficient if $M((W_i,w_i)) = (x',p)$ with $\sum_{i \in N}v_i(x') \geq \frac{1}{\alpha}\max_{x \in X}v_i(c)$

Thm. 5.11: No $\bigO(\abs{E}^{1/2-\eps})$-efficient polynomial mechanism for any $\eps \gt 0$
Thm. 5.11: for single minded bidders unless NP $\subseteq$ ZPP

Maximum Independent Set:
Input: undirectd graph $D=(V,E)$
Output: set $I \subseteq V$ with $\set{u,v} \notin E$ f.a. $u,v \in I$
Output: such that $\abs{I}$ maximal

Fact: Maximum Independent Set is NP-hard.

Fact: No polynomial $\bigO(\abs{V}^{1-\eps})$-approximation algorithm
Fact: for Maximum Independent Set unless NP $\subseteq$ ZPP

Greedy Mechanism

Input: bids $(B_i,b_i) \in \PSet{E} \times \IRnn$ for all $i \in N$
Output: winners $N' \subseteq N$ and payments $p \in \IRnn^{N'}$

sort players s.th. $\frac{b_1}{\sqrt{\abs{B_1}}} \geq \frac{b_2}{\sqrt{\abs{B_2}}} \geq \dots \geq \frac{b_n}{\sqrt{\abs{B_n}}}$; init. $N' \leftarrow \emptyset$
For $i \in N$ Do
mm If $B_i \cap B_j = \emptyset$ f.a. $j \in N'$ Then $N' \leftarrow N' \cup \set{i}$
For $i \in N'$ Do
mm set $j \leftarrow \inf\Set{j' \gt i \SMid \begin{array}{l}B_i \cap B_{j'} \neq \emptyset \text{ and }\\ B_k \cap B_{j'} = \emptyset \text{ f.a. } k \lt j', k \in N'\setminus\set{i}\end{array}}$
mm If $j \neq \infty$ Then $p_i \leftarrow \frac{b_j}{\sqrt{\abs{B_j}}}\sqrt{\abs{B_i}}$ Else $p_i \leftarrow 0$

Lem. 5.9: mechanism for single-minded bidders is sp if

$i$ wins with $(B_i,b_i)$, $B'_i \subseteq B_i$ and $b'_i \geq b_i$
$\implies i$ wins with $(B'_i,b'_i)$ as well (Monotonicity)
$i$ wins with $(B_i,b_i)$ and pays $p_i$
$\implies p_i = \min\set{b_i' \sMid (B_i,b'_i) \text{ wins}}$ (critical value)
$i$ does not win $\implies p_i=0$

Lem. 5.10: Under truthful bidding Greedy finds $N'$ with
$\sum_{i \in N'}w_i \geq \frac{1}{\sqrt{\abs{E}}}\max\set{\sum_{i \in N^*}w_i \sMid N^* \subseteq N \text{ solution}}$

Thm. 5.8: Greedy is strategyproof, $\sqrt{\abs{E}}$-efficient, poly.

§5.5 Single-Parameter Environments

a single type of item
multiple players $N = \set{1,\dots,n}$
private per unit value $v_i \in \IRnn$
players declare per unit bid $b_i \in \IRnn$
set of possible allocations $X \subseteq \IRnn^N$
⤳ $x \in X$ ≙ $i$ gets $x_i$ units
mechanism $M: \IRnn^N \to X \times \IRnn^N, b \mapsto (x,p)$
with payment $p_i \leq x_i\cdot v_i$
$i$'s utility of $M(b)=(x,p)$ is $u_e(x,p) \coloneqq x_i\cdot v_i - p_i$

Generic Mechanism

Input: per unit bids $b \in \IRnn^N$
Output: allocation $x$ and payments $p \in \IRnn^N$

compute alloction $x(b) \in X$ "allocation rule"
compute payments $p(b) \in \IRnn^N$ "payment rule"

allocation rule $x: \IRnn^N \to X$ is implementable
$\coloniff \exists$ payment rule $p: \IRnn^N \to \IRnn^N$
s.th. the above mechanism is strategyproof

Examples:

single item: $x \in \set{0,1}^N$ with $\sum_i x_i=1$ 🍎
identical items: $x \in \set{0,1}^N$ with $\sum_i x_i \leq k$ 🍎🍎🍎
Sponsored Search Auction $x: N \to \set{\alpha_1 \geq \dots \geq \alpha_k, 0, \dots, 0}$

Thm. 5.18 (Myerson's Lemma):
For piece-wise constant (in each player's bid) allocation rules $x$ we have:

$x$ implementable $\iff x$ monoton
$x$ implementable $\iff x$ i.e., $z \leq y \implies x_i(z,b_{-i}) \leq x_i(y,b_{-i})$
$x$ implementable $\implies \exists$ unique implementing payment rule
$x$ implementable $\implies$ payment rule defined by $p_i(b) \coloneqq \sum_{j=1}^\ell z_j h_j$
mmm where $z_j$ are jump points of $x_i(\_,b_{-i})$ until $b_i$ with height $h_j$